package com.study.daily.algozuo.y2021.m12.day1212;

/**
 * @author Tom on 2021/12/12
 */
public class Code02_MinStickers {
    public static void main(String[] args) {

    }

    public static int minStickers1(String[] stickers, String target) {
        int ans = process1(stickers, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process1(String[] stickers, String target) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < stickers.length; i++) {
            String rest = minus(stickers[i], target);
            if (rest.length() != target.length()) {
                min = Math.min(min, process1(stickers, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    public static String minus(String s1, String s2) {
        int[] counts = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
        }
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0) {
                for (int j = 0; j < counts[i]; j++) {
                    str.append((char) ('a' + i));
                }
            }
        }
        return str.toString();
    }

    public static int minStackers(String[] stickers, String target) {
        int N = stickers.length;
        int[][] stickerCounts = new int[N][26];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < stickers[i].length(); j++) {
                stickerCounts[i][stickers[i].charAt(j) - 'a']++;
            }
        }
        int ans = process2(stickerCounts, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process2(int[][] stickerCounts, String target) {
        int[] targetCount = new int[26];
        for (int i = 0; i < target.length(); i++) {
            targetCount[target.charAt(i) - 'a']++;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < stickerCounts.length; i++) {
            int[] sticker = stickerCounts[i];
            if (sticker[target.charAt(i) - 'a'] > 0) {
                StringBuilder str = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    if (targetCount[j] > 0) {
                        int num = targetCount[j] - sticker[j];
                        for (int k = 0; k < num; k++) {
                            str.append((char) ('a' + j));
                        }
                    }
                }
                min = Math.min(min, process2(stickerCounts, str.toString()));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }
}
